package com.zpself.module.算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 * @Description 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，返回 -1。
 * 你可以认为每种硬币的数量是无限的。
 *
 * @date in  2021/1/20 19:13
 * @Modified By
 */
public class 力扣_322_零钱兑换 {
    public static void main(String[] args) {
        int[] coins  = {1, 2, 5};
        System.out.println(myAnswer(coins ,3));
        System.out.println(myAnswer(coins ,-1));
        System.out.println(myAnswer(coins ,0));
        System.out.println(myAnswer(coins ,7));
        System.out.println(myAnswer(coins ,8));
        System.out.println(myAnswer(coins ,9));
        System.out.println(myAnswer(coins ,10));
    }

    /**
    * @param  coins 币值数组
    * @param  amount 金额
     *
     * f(n) = min(f(n-c1) , f(n-c2) , f(n-c3)  )+1
    **/
    public  static  int myAnswer(int[] coins, int amount){
        if(amount<0)
            return -1;
        if(amount==0)
            return amount;

        int[] dp = new int[amount+1];//把1到amount的都记录起来，动态规划：通过小的来计算大的
        for (int i = 1; i <=amount; i++) {
            int min =Integer.MAX_VALUE;
            for (int coin : coins) {//获取所有方案的最小值  f(n) = min(f(n-c1) , f(n-c2) , f(n-c3)  )+1
                if (i - coin >= 0 && dp[i - coin] != -1)//判断  dp[i - coin] 是否存在
                    min = min>(dp[i - coin] + 1) ? (dp[i - coin] + 1) : min;
            }
            dp[i]=min==Integer.MAX_VALUE?-1 :min;
        }
        return dp[amount];
    }
}
